﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Util.Data
{
    public static class ListExtensions
    {
        /// <summary>
        /// Finds the index of the an element that compares equal using the
        /// given predicate. If there are multiple such elements, return any
        /// one of them. If no such element exists, returns the index of the
        /// first element that follows. In this case, you need to bit-wise
        /// negate the returned index.
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list"></param>
        /// <param name="compare"></param>
        /// <returns></returns>
        public static int BinarySearch<T1, T2>(
            this IList<T1> list, T2 value, int startIndex, int count, LooseComparison<T1, T2> compare)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (compare == null)
                throw new ArgumentNullException("compare");
            if (startIndex < 0 || startIndex > list.Count)
                throw new ArgumentOutOfRangeException("startIndex");
            if (count < 0 || count > list.Count - startIndex)
                throw new ArgumentOutOfRangeException("count");

            int lb = startIndex, ub = startIndex + count;
            while (lb < ub)
            {
                int i = lb + (ub - lb) / 2;
                int cmp = compare(list[i], value);
                if (cmp == 0)
                    return i;
                if (cmp < 0)
                    lb = i + 1;
                else
                    ub = i;
            }
            return ~lb;
        }

        public static int BinarySearch<T1, T2>(
            this IList<T1> list, T2 value, LooseComparison<T1, T2> compare)
        {
            return BinarySearch<T1, T2>(list, value, 0, list.Count, compare);
        }

#if false
        public static int BinarySearch<T>(
           this IList<T> list, T value, int startIndex, int count, Comparison<T> compare)
        {
            return BinarySearch<T, T>(
                list, value, startIndex, count, (x, y) => compare(x, y));
        }

        public static int BinarySearch<T>(
            this IList<T> list, T value, Comparison<T> compare)
        {
            return BinarySearch<T>(list, value, 0, list.Count, compare);
        }
#endif

        public static T[] Slice<T>(this IList<T> list, int offset, int count)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            if (offset < 0 || offset > list.Count)
                throw new ArgumentOutOfRangeException("offset");
            if (count < 0 || count > list.Count - offset)
                throw new ArgumentOutOfRangeException("count");

            T[] result = new T[count];
            for (int i = 0; i < count; i++)
            {
                result[i] = list[offset + i];
            }
            return result;
        }
    }

    public delegate int LooseComparison<T1, T2>(T1 x, T2 y);


}
